package Bloom;

import java.util.BitSet;

/**
 * 布隆过滤器
 * 布隆过滤器能告诉你某个数可能存在或者一定不存在
 * 用于对与海量的字符串的存储
 * 通过哈希算出该字符串的一个地址，再把这个地址映射再位图中
 * 这里不会只用到一个哈希函数，而是使用多个哈希函数去表示一个字符串
 * 这样能减少误判的概率
 */
public class BloomFilter {
    private static final int DEFAULT_SIZE = 1 << 24 ;//方便哈希函数的计算
    int[] randomArr = {4, 33, 7};//用于实现不同的哈希函数
    BitSet bitSet = new BitSet(DEFAULT_SIZE);



    public boolean push(String s) {
        for (int i = 0; i < randomArr.length; i++) {//用来遍历这个数组
            bitSet.set(simpleHash(randomArr[i], s));
        }
        return true;
    }
    public boolean push(long s) {
        for (int i = 0; i < randomArr.length; i++) {//用来遍历这个数组
            bitSet.set(simpleHash(randomArr[i], s+""));
        }
        return true;
    }

    public boolean contain(String s) {
        if (s == null) {
            return false;
        }
        for (int i : randomArr) {
            if (!bitSet.get(simpleHash(i, s))) {
                return false;
            }
        }
        return true;
    }
    public boolean contain(long s) {
        for (int i : randomArr) {
            if (!bitSet.get(simpleHash(i, s+""))) {
                return false;
            }
        }
        return true;
    }
    private int simpleHash(int r, String s) {
        return r * s.hashCode() > 0 ? r * s.hashCode()/114514 : -(r * s.hashCode() / 114514);
    }
}